package com.xy6.algo.divide;

/**
 * 大整数相乘
 * 
 * <pre>
 * 假设一个数X，位数为n，另一个数Y，位数为n
 * 法一：
 * 按照数学中乘法计算规则，X*Y时间复杂度为O(n^2)
 * 
 * 法二：
 * 将X分为前n/2位、后n/2位，将Y分为前n/2位，后n/2位
 * X*Y
 * =(A*10^(n/2)+B)*(C*10^(n/2)+D)
 * =A*C*10^n+(A*D+B*C)*10^(n/2)+B*D  //用到4次乘法（AC、AD、BC、BD），3次加法
 * =A*C*10^n+((A-B)*(D-C)+AC+BD)*10^(n/2)+B*D  //用到3次乘法（AC、()*()、BD），6次加法
 * T(n)=3T(n/2)+O(n)  //根据Master定理对该公式进行推导
 * T(n)=O(n^以2为底3的对数)
 * =O(n^1.58)
 * 分治法求解时间复杂度为O(n^1.58)
 * http://blog.csdn.net/chhuach2005/article/details/21168179
 * 递归次数计算：
 * x=log2^(n/8)，x向上取整，位数小于4时，直接计算，因此出现8.
 * t=3^x+1/2(3^x-1)O(n)
 * 实验证明，递归次数较多，且O(n)耗时较久，导致该方法耗时大于法一。
 * O(n)耗时的原因：
 * 字符串加减实现，负号处理
 * 
 * 法三：
 * 两数位数不同
 * 1234*34567
 * X*Y
 * =A*C*10^(m2+n2)+A*C*10^(m2+n2)+(A*10^m2-B)(D-C*10^n2)+BD+BD
 * https://www.cnblogs.com/little-kwy/archive/2017/09/30/7613642.html
 * 非理想状态下，该公式可能存在递归死循环，需提前对结尾的0处理
 * 
 * 此方案不可行，两个7位数相乘，递归1869次，发生堆栈溢出。
 * 中间两个表达式相乘时，收敛速度慢，导致递归次数过多，发生堆栈溢出。
 * 尝试将两数位数补齐为相同位数，如01234*34567，再进行计算。
 * 
 * </pre>
 * 
 * @author zhang
 * @since 2018-01-30
 */
public class BigNumMultiply {
	
	public static int count = 0;

	public static void main(String[] args) {
		// System.out.println(multiplyForce("123", "3456"));
		System.out.println(plusPositive("123", "5"));
		System.out.println(plusPositive("123", "7"));

		System.out.println(minusPositive("123", "5"));
		System.out.println(minusPositive("123", "25"));

		System.out.println(power("123", 0));
		System.out.println(power("123", 3));
	}

	/**
	 * 计算两个大整数相乘
	 * 
	 * <pre>
	 * 逐位相乘，再累加
	 * </pre>
	 * 
	 * @param str1
	 * @param str2
	 * @return
	 */
	public static String multiplyForce(String str1, String str2) {
		// 处理负数
		int sign = sign(str1) * sign(str2);
		if(sign == 1){
			str1 = replace(str1);
			str2 = replace(str2);
		} else if(sign == 0){
			return "0";
		} else {
			return "-" + multiplyForce(replace(str1), replace(str2));
		}
		int len1 = str1.length();
		int len2 = str2.length();
		int[] num1 = new int[len1];
		int[] num2 = new int[len2];
		int len = len1 + len2 + 1;
		int[] num = new int[len];
		for (int i = 0; i < len1; i++) {
			num1[i] = Integer.valueOf(String.valueOf(str1.charAt(i)));
		}
		for (int i = 0; i < len2; i++) {
			num2[i] = Integer.valueOf(String.valueOf(str2.charAt(i)));
		}
		// 逐位相乘
		for (int j = len2 - 1; j >= 0; j--) {
			for (int i = len1 - 1; i >= 0; i--) {
				int pos = len1 - i + len2 - j - 1;
				num[len - pos] += num1[i] * num2[j];
			}
		}
		// 进位
		for (int i = len - 1; i >= 1; i--) {
			if (num[i] < 10) {
				continue;
			}
			num[i - 1] += num[i] / 10;
			num[i] = num[i] % 10;
		}
		// 处理头部的0
		int first = 0;
		while (first < len && num[first] == 0) {
			first++;
		}
		// 拼接计算结果
		String s = "";
		for (int i = first; i < len; i++) {
			s += num[i];
		}

		return s;
	}

	/**
	 * 分治法计算大正整数相乘。大整数位数可以不同
	 * 
	 * <pre>
	 * 1234*3456
	 * A*C*10^(m2+n2)+A*C*10^(m2+n2)+(A*10^m2-B)(D-C*10^n2)+BD+BD
	 * 
	 * https://www.cnblogs.com/little-kwy/archive/2017/09/30/7613642.html
	 * </pre>
	 * 
	 * @param str1
	 * @param str2
	 * @return
	 */
	public static String multiply(String str1, String str2) {
		count++;
//		System.out.println(String.format("%d, %s, %s", count, str1, str2));
		if (str1.length() <= 4 && str2.length() <= 4) {
			return String.valueOf(Long.valueOf(str1) * Long.valueOf(str2));
		}
		// 处理负号。为减少一次递归，采用标识位实现
		int sign = sign(str1) * sign(str2);
		if(sign == 0){
			return "0";
		} else {
			str1 = replace(str1);
			str2 = replace(str2);
		}
		// 位数补齐
		int m = str1.length();
		int n = str2.length();
		int max = m > n ? m : n;
		for (int i = 0; i < max - m; i++) {
			str1 = "0" + str1;
		}
		for (int i = 0; i < max - n; i++) {
			str2 = "0" + str2;
		}
		int n1 = max/2;
		int n2 = max - n1;
		// str1 = AB
		String A = deleteZero(str1.substring(0, n1));
		String B = deleteZero(str1.substring(n1));
		// str2 = CD
		String C = deleteZero(str2.substring(0, n1));
		String D = deleteZero(str2.substring(n1));
		
		String P1 = "";
		if (A.length() <= 4 && C.length() <= 4) {
			P1 = String.valueOf(Long.valueOf(A) * Long.valueOf(C));
		} else {
			P1 = multiply(A, C);
		}
		String S1 = power(P1, n2 + n2);
		String S2 = "";
		if (n2 <= 4) {
			S2 = String.valueOf(Long.valueOf(B) * Long.valueOf(D));
		} else {
			S2 = multiply(B, D);
		}
		String P3 = minus(A,B);
		String P4 = minus(D,C);
		String P5 = "";
		
		if(P3.length() <= 4 && P4.length() <= 4){
			P5 = String.valueOf(Long.valueOf(P3) * Long.valueOf(P4));
		} else {
			P5 = multiply(P3, P4);
		}
		String S3 = power(plus(plus(P5, P1), S2), n2);

		String S = plus(plus(S1, S3), S2);
		return sign == -1 ? addSymbol("-", S) : S;
	}
	
	/**
	 * 替换一个字符串中的负号
	 * 
	 * @param s
	 * @return
	 */
	private static String replace(String str1){
		return str1.charAt(0) == '-' ? str1.substring(1) : str1;
	}
	
	/**
	 * 判断一个字符串的符号位
	 * <pre>
	 * 正：1
	 * 负：-1
	 * 零：0
	 * </pre>
	 * 
	 * @param s
	 * @return
	 */
	private static int sign(String s){
		if(s.charAt(0) == '-'){
			return -1;
		} else if("0".equals(s)){
			return 0;
		} else {
			return 1;
		}
	}

	/**
	 * 去除一个正数头部的0
	 * 
	 * @param s
	 * @return
	 */
	public static String deleteZero(String s){
		if(s.charAt(0) != '0'){
			return s;
		}
		// 去掉头部的0
		int len = s.length();
		int start = 0;
		while (start < len - 1 && s.charAt(start) == '0') {
			start++;
		}
		String s2 = "";
		for (int i = start; i < len; i++) {
			s2 += String.valueOf(s.charAt(i));
		}
		return s2;
	}
	
	/**
	 * 拼接操作符、字符串，处理字符串为0的场景
	 * 
	 * @param symbol
	 * @param s
	 * @return
	 */
	private static String addSymbol(String symbol, String s) {
		int sign = sign(s);
		if (sign == 1) {
			return symbol + s;
		} else if(sign == 0){
			return "0";
		} else {
			return s.substring(1);
		}
	}

	/**
	 * 计算s*10^n，返回一个字符串
	 * 
	 * @param s
	 * @param num
	 * @return
	 */
	public static String power(String s, int num) {
		if ("0".equals(s)) {
			return "0";
		}
		for (int i = 0; i < num; i++) {
			s += "0";
		}
		return s;
	}

	/**
	 * 两个字符串相减
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static String minus(String s1, String s2) {
		if (s1.charAt(0) != '-' && s2.charAt(0) != '-') {
			// 两个正数
			int len1 = s1.length();
			int len2 = s2.length();
			if (len1 > len2 || (len1 == len2 && s1.compareTo(s2) > 0)) {
				return minusPositive(s1, s2);
			} else if (s1.equals(s2)) {
				return "0";
			} else {
				return addSymbol("-", minusPositive(s2, s1));
			}
		} else if (s1.charAt(0) != '-' && s2.charAt(0) == '-') {
			// 一个正数，一个负数
			return plusPositive(s1, s2.substring(1));
		} else if (s1.charAt(0) == '-' && s2.charAt(0) != '-') {
			// 一个负数，一个正数
			return addSymbol("-", plusPositive(s1.substring(1), s2));
		} else {
			// 两个负数
			s2 = s2.substring(1);
			s1 = s1.substring(1);
			return minus(s2, s1);
		}
	}

	/**
	 * 两个正数字符串相减，第一个数一定大于等于第二个数
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	private static String minusPositive(String s1, String s2) {
		if (s1.equals(s2)) {
			return "0";
		}
		int len1 = s1.length();
		int len2 = s2.length();
		int[] a1 = new int[len1];
		int[] a2 = new int[len2];
		int[] a = new int[len1];
		for (int i = 0; i < len1; i++) {
			a1[i] = Integer.valueOf(String.valueOf(s1.charAt(i)));
		}
		for (int i = 0; i < len2; i++) {
			a2[i] = Integer.valueOf(String.valueOf(s2.charAt(i)));
		}
		for (int i = 0; i < len1; i++) {
			int num1 = a1[len1 - 1 - i];
			int num2 = 0;
			if (len2 - 1 - i >= 0) {
				num2 = a2[len2 - 1 - i];
			}
			int m = num1 - num2 + a[len1 - 1 - i];
			if (m < 0) {
				a[len1 - 2 - i]--;
				m += 10;
			}
			a[len1 - 1 - i] = m;
		}
		String s = "";
		int start = 0;
		while (start < len1 && a[start] == 0) {
			start++;
		}
		for (int i = start; i < len1; i++) {
			s += String.valueOf(a[i]);
		}
		return s;
	}

	/**
	 * 两个字符串相加
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static String plus(String s1, String s2) {
		if (s1.charAt(0) != '-' && s2.charAt(0) != '-') {
			// 两个正数
			return plusPositive(s1, s2);
		} else if (s1.charAt(0) != '-' && s2.charAt(0) == '-') {
			// 一个正数，一个负数
			return minus(s1, s2.substring(1));
		} else if (s1.charAt(0) == '-' && s2.charAt(0) != '-') {
			// 一个负数，一个正数
			return minus(s2, s1.substring(1));
		} else {
			// 两个负数
			return addSymbol("-", plusPositive(s1.substring(1), s2.substring(1)));
		}
	}

	/**
	 * 两个正数字符串相加
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	private static String plusPositive(String s1, String s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		int[] a1 = new int[len1];
		int[] a2 = new int[len2];
		for (int i = 0; i < len1; i++) {
			a1[i] = Integer.valueOf(String.valueOf(s1.charAt(i)));
		}
		for (int i = 0; i < len2; i++) {
			a2[i] = Integer.valueOf(String.valueOf(s2.charAt(i)));
		}
		int len = len1 > len2 ? (len1 + 1) : (len2 + 1);
		int[] a = new int[len];
		// 逐位相加
		for (int i = 0; i < len; i++) {
			int num1 = 0;
			if (len1 - 1 - i >= 0) {
				num1 = a1[len1 - 1 - i];
			}
			int num2 = 0;
			if (len2 - 1 - i >= 0) {
				num2 = a2[len2 - 1 - i];
			}
			int s = num1 + num2 + a[len - 1 - i];
			if (s >= 10) {
				// 进1
				a[len - 2 - i] += 1;
				s = s - 10;
			}
			a[len - 1 - i] = s;
		}
		String s = "";
		// 去掉头部的0
		int start = 0;
		while (start < len- 1 && a[start] == 0) {
			start++;
		}
		for (int i = start; i < len; i++) {
			s += String.valueOf(a[i]);
		}
		return s;
	}
}
